package q84

func largestRectangleArea(heights []int) int {
	var max = 0
	for i := 0; i < len(heights); i++ {
		tmp := largestRectangleAreaByIndex(heights, i)
		if tmp > max {
			max = tmp
		}
	}
	return max
}

func largestRectangleAreaByIndex(heights []int, index int) int {
	left := index - 1
	right := index + 1
	h := heights[index]

	for ; left >= 0; left-- {
		if heights[left] < h {
			break
		}
	}
	for ; right < len(heights); right++ {
		if heights[right] < h {
			break
		}
	}

	left++
	right--

	area := (right - left + 1) * h
	//log.Printf("%d,%d=%d",left,right,area)
	return area
}
